package B刷题.A栈和队列;

import java.util.LinkedList;

/**
 * @author wei.zhao
 * @description: 程序员代码面试指南：滑动窗口最大值
 * @date 2022/12/6 14:38
 */
public class Code08_GetMaxWindow {

    /**
     * 每个下标最多进队列一次、出队列一次，所以时间复杂度是O(N)；
     * 队列中维护的实际上是成为最大值的可能性。
     */
    public int[] getMaxWindow(int[] nums, int k) {
        if (null == nums || nums.length == 0 || k == 0) {
            return null;
        }
        int[] result = new int[nums.length - k + 1];
        LinkedList<Integer> list = new LinkedList<>();
        for (int i = 0; i < nums.length; i++) {
            // 队列不为空、队列末尾元素小于当前元素，当前元素不再可能成为最大值，弹出
            while (!list.isEmpty() && nums[list.peekLast()] <= nums[i]) {
                list.pollLast();
            }
            list.add(i);
            // 弹出前面的元素
            if (list.peekFirst() == i - k) {
                list.pollFirst();
            }
            // 当前窗口最大值放入数组
            if (i >= k - 1) {
                result[i-k+1]=nums[list.peekFirst()];
            }
        }
        return result;
    }

}
